5.5 KB · ⇊ 2 parts · ⤓ Micron 5.5 KB · ⤓ HTML 15.7 KB

top

Nella mwawteoria della complessità, mwbaEXPSPACE è l'mwbqinsieme di tutti i problemi di decisione risolvibili da una mwbwmacchina deterministica di Turing nello spazio mwcaO(2mwcqmwcgp(mwcwn)), dove mwdap(mwdqn) è una funzione polinomiale di mwdgn. (Alcuni autori restringono mwdwp(mwean) all'essere una mweqfunzione lineare, ma la maggior parte degli autori invece chiamano la classe risultante mwegESPACE.) Se usiamo invece una macchina non deterministica, otteniamo la classe mwfaNEXPSPACE, che è uguale a mwfqEXPSPACE per il mwfgteorema di Savitch.

In termini di mwgaDSPACE e mwggNSPACE,

mwhg EXPSPACE = ⋃ ⋃ k ∈ ∈ N DSPACE ( 2 n k ) = ⋃ ⋃ k ∈ ∈ N NSPACE ( 2 n k ) {\displaystyle {\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})}

Un problema di decisione è mwiaEXPSPACE-completo se è in mwiqEXPSPACE, e ogni problema in mwigEXPSPACE ha una riduzione di tempo polinomiale ad esso. In altre parole, c'è un mwjaalgoritmo di tempo polinomiale che trasforma richieste dell'uno in richieste dell'altro con la stessa risposta. I problemi mwjqEXPSPACE-completi potrebbero essere pensati come i problemi più difficili in mwjgEXPSPACE.

mwkaEXPSPACE è un superinsieme stretto di mwkqmwkgPSPACE, mwkwmwlaNP e mwlqmwlgP e si crede sia un superinsieme stretto di mwlwmwmaEXPTIME.

Un esempio di un problema mwmgEXPSPACE-completo è quello di riconoscere se due mwmwespressioni regolari rappresentano linguaggi diversi, dove le espressioni sono limitate a quattro operatori: unione, mwnaconcatenazione, la mwnqstella di Kleene (zero o più copie di un'espressione) e quadratura (due copie di un'espressione).cite-ref-1[1]

Se si tralascia la stella di Kleene, allora quel problema diventa mwowmwpaNEXPTIME-completo, che è come mwpqEXPTIME-completo, tranne che è definito in termini di mwpgmacchine di Turing non deterministiche anziché deterministiche.

È stato anche mostrato da L. Berman nel 1980 che il problema di verificare/falsificare una qualsiasi affermazione del mwqaprimo ordine sui mwqqnumeri reali che implichi soltanto l'mwqgaddizione e il confronto (ma non la mwqwmoltiplicazione) è in mwraEXPSPACE.

• Note

• Bibliografia

cite-note-11. ↑ Meyer, A.R. and L. Stockmeyer. mwtaThe equivalence problem for regular expressions with squaring requires exponential space. mwtq13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

• L. Berman mwuqThe complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.

• mwuwMichael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN 0-534-94728-X. Sezione 9.1.1: "Exponential space completeness", pp.mwva 313–317. Dimostra che determinare l'equivalenza delle espressioni regolari con l'esponenziazione è EXPSPACE-completo.